#if !defined(SET_MARK_DIFF_H)
#define SET_MARK_DIFF_H
// set_mark_diff.h : helper functions and macros
//
/////////////////////////////////////////////////////////////////////////////


#include <algorithm>
#include <iterator>
#include <functional>
/*****************************************************************************************
						set_mark_diff
******************************************************************************************/
namespace
{
template<class InIt1, class OP_MARK>
inline
void PRIVATE_mark_all(InIt1 i, InIt1 last, OP_MARK op_mark)
{
	while (i != last)
	{
		op_mark(*i);
		++i;
	}

}
}
//
//	Store whether items from
//			i1 -> last1 and 
//			i2 -> last2 are unique
// 		if they are unique, 
//			run op_mark1(*i1) or 
//				op_mark2(8i2
template<class _InIt1, class _InIt2, class PRED_Less, class OP_MARK1, class OP_MARK2>
inline
void set_mark_diff(	_InIt1 i1, _InIt1 last1,
					_InIt2 i2, _InIt2 last2,
					PRED_Less pred_less,
					OP_MARK1 op_mark1,
					OP_MARK2 op_mark2)
{
	if (i1 == last1)
	{
		PRIVATE_mark_all(i2, last2, op_mark2);
		return;
	}
	if (i2 == last2)
	{
		PRIVATE_mark_all(i1, last1, op_mark1);
		return;
	}

	for (;;)
	{
		if (pred_less(*i1, *i2))
		{
			op_mark1(*i1);
			if (++i1 == last1)
				break;
		}
		else if (pred_less(*i2, *i1))
		{
			op_mark2(*i2);
			if (++i2 == last2)
				break;
		}
		else
		{
			++i1;
			++i2;
			if (i1 == last1 || i2 == last2)
				break;
		}
	}

	// mark all the rest
	if (i1 == last1)
		PRIVATE_mark_all(i2, last2, op_mark2);
	else if (i2 == last2)
		PRIVATE_mark_all(i1, last1, op_mark1);
}

//
//	Store whether items from
//			i1 -> last1 and 
//			i2 -> last2 are unique
// 		if they are unique, 
//			run op_markdiff1(*i1) or 
//				op_markdiff2(*i2)
// 		else
//			run op_mark1(*i1) or 
//				op_mark2(*i2)
template<class _InIt1, class _InIt2, class PRED_Less, class OP_MARKDIFF1, class OP_MARKDIFF2, 
		class OP_MARKIDENTICAL1, class OP_MARKIDENTICAL2>
inline
void set_mark_overlap(	_InIt1 i1, _InIt1 last1,
						_InIt2 i2, _InIt2 last2,
						PRED_Less pred_less,
						OP_MARKDIFF1 op_markdiff1,
						OP_MARKDIFF2 op_markdiff2,
						OP_MARKIDENTICAL1 op_markidentical1,
						OP_MARKIDENTICAL2 op_markidentical2)
{
	if (i1 == last1)
	{
		PRIVATE_mark_all(i2, last2, op_markdiff2);
		return;
	}
	if (i2 == last2)
	{
		PRIVATE_mark_all(i1, last1, op_markdiff1);
		return;
	}

	for (;;)
	{
		if (pred_less(*i1, *i2))
		{
			op_markdiff1(*i1);
			if (++i1 == last1)
				break;
		}
		else if (pred_less(*i2, *i1))
		{
			op_markdiff2(*i2);
			if (++i2 == last2)
				break;
		}
		// the same
		else
		{
			op_markidentical1(*i1);
			op_markidentical2(*i2);
			++i1;
			++i2;
			if (i1 == last1 || i2 == last2)
				break;
		}
	}

	// mark all the rest
	if (i1 == last1)
		PRIVATE_mark_all(i2, last2, op_markdiff2);
	else if (i2 == last2)
		PRIVATE_mark_all(i1, last1, op_markdiff1);
}

/*****************************************************************************************
						set_mark_diff
******************************************************************************************/
namespace
{
template<class InIt1, class InIt2, class OP_MARK>
inline
void PRIVATE_mark_all(InIt1 i, InIt1 last, InIt2 unique_to_set, OP_MARK op_mark)
{
	while (i != last)
	{
		op_mark(*unique_to_set++);
		++i;
	}

}
}

//
//	Store whether items are unique in flagged_unique_to_set1 and flagged_unique_to_set2
// 		These are incremented the same number of times as the last - i
// 		i.e. Pass two container of flags with the same size() as the containers
// 		to compare
//	The flagged containers are tagged using op_mark1 and op_mark2
template<class InIt1, class InIt2, class InIt3, class InIt4, class PRED_Less,
													class OP_MARK1, class OP_MARK2>
inline
void set_mark_diff(	InIt1 i1, InIt1 last1,
					InIt2 i2, InIt2 last2,
					InIt3 flagged_unique_to_set1,
					InIt4 flagged_unique_to_set2,
					PRED_Less pred_less,
					OP_MARK1 op_mark1,
					OP_MARK2 op_mark2)
{
	//
	//	Set 1 absent
	//	All of set 2 to is marked to be unique
	//
	if (i1 == last1)
	{
		PRIVATE_mark_all(i2, last2, flagged_unique_to_set2, op_mark2);
		return;
	}


	//
	//	Set 2 absent
	//	All of set 1 to is marked to be unique
	//
	if (i2 == last2)
	{
		PRIVATE_mark_all(i1, last1, flagged_unique_to_set1, op_mark1);
		return;
	}


	//
	//	If set 1 is ahead, mark set to and vice versa
	//
	for (;;)
	{
		if (pred_less(*i1, *i2))
		{
			op_mark1(*flagged_unique_to_set1++);
			// stop at end of set1
			if (++i1 == last1)
				break;
		}
		else if (pred_less(*i2, *i1))
		{
			op_mark2(*flagged_unique_to_set2++);
			// stop at end of set2
			if (++i2 == last2)
				break;
		}
		else
		{
			// they are the same, mark neither
			++i1;
			++flagged_unique_to_set1;
			++i2;
			++flagged_unique_to_set2;
			// if end of either, end
			if (i1 == last1 || i2 == last2)
				break;
		}
	}

	//
	//	Mark all in the other set if run out of members of one set
	//
	if (i1 == last1)
		PRIVATE_mark_all(i2, last2, flagged_unique_to_set2, op_mark2);
	else if (i2 == last2)
		PRIVATE_mark_all(i1, last1, flagged_unique_to_set1, op_mark1);
}


// wrapper for containers
template<class CONT1, class CONT2, class PRED_Less, class OP_MARK1, class OP_MARK2>
inline
void set_mark_diff_cont(	const CONT1& c1, 
							const CONT2& c2,
							PRED_Less pred_less,
							OP_MARK1 op_mark1,
							OP_MARK2 op_mark2)
{
	set_mark_diff(	c1.begin(), 
					c1.end(), 
					c2.begin(),
					c2.end(),
					pred_less,
					op_mark1,
					op_mark2);
}


// wrapper for containers
template<class CONT1, class CONT2, class InIt3, class InIt4, 
				class PRED_Less, class OP_MARK1, class OP_MARK2>
inline
void set_mark_diff_cont(const CONT1& c1, 
						const CONT2& c2,
						InIt3 flagged_unique_to_set1,
						InIt4 flagged_unique_to_set2,
						PRED_Less pred_less,
						OP_MARK1 op_mark1,
						OP_MARK2 op_mark2)
{
	set_mark_diff(	c1.begin(), 
					c1.end(), 
					c2.begin(),
					c2.end(),
					flagged_unique_to_set1,
					flagged_unique_to_set2,
					pred_less,
					op_mark1,
					op_mark2);
}


template<class CONT1, class CONT2, class PRED_Less, class OP_MARKDIFF1, class OP_MARKDIFF2, 
		class OP_MARKIDENTICAL1, class OP_MARKIDENTICAL2>
inline
void set_mark_overlap_cont(	const CONT1& c1, 
							const CONT2& c2,
							PRED_Less pred_less,
							OP_MARKDIFF1 op_markdiff1,
							OP_MARKDIFF2 op_markdiff2,
							OP_MARKIDENTICAL1 op_markidentical1,
							OP_MARKIDENTICAL2 op_markidentical2)
{
	set_mark_overlap(	c1.begin(), 
						c1.end(), 
						c2.begin(),
						c2.end(),
						pred_less,
						op_markdiff1, 
						op_markdiff2, 
						op_markidentical1,
						op_markidentical2);
}
#endif	//SET_MARK_DIFF_H
